package 动态规划;

/**
 * 1248. 统计「优美子数组」
 * 给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
 * 请返回这个数组中 「优美子数组」 的数目。
 *
 * 思路：采用滑动窗口的解法，具体步骤如下：
 *  1：滑动窗口的定义：
 *      使用两个指针 left 和 Right 来表示当前窗口的左右边界
 *      维护一个变量oldCnt来记录当前窗口中奇数的数量
 *  2：窗口的扩展与收缩：
 *      - 右指针 Right 不断向右移动，扩展窗口，直到该窗口内包含k个奇数
 *      - 当滑动窗口中包含k个奇数时，计算当前窗口中拥有优美子数组的数量
 *      - 左指针left 继续向右移动，收缩窗口，直到窗口中包含的奇数数量小于K
 *  3：计算优美子数组的数量：
 *      当窗口中包含k个奇数时，计算窗口左侧与右侧的偶数数量；
 *      优美子数组的数量为左侧偶数数量加1 * 右侧偶数数量加1
 *  4：结果累加：
 *      将每次计算得到的优美子数组数量累加到结果中.
 */
public class L_1248 {

    public int numberOfSubarrays(int[] nums, int k) {
        // 定义左边界，右边界，奇数数量，结果
        int left = 0, right = 0, oddCnt = 0, res = 0;
        while (right < nums.length){
            // 右指针先右
            if (nums[right] % 2 == 1){
                oddCnt++; // 奇数数量加1
            }
            right++;
            // 如果滑动窗口内有k个奇数
            if (oddCnt == k){
                // 开始计算到右边界的个数
                int temp = right;
                // 右边界的偶数个数，终止条件是知道右边界的下一个为奇数
                while (right < nums.length && nums[right] % 2 == 0){
                    right++;
                }
                int rightCnt = right - temp;
                // 计算左边界的个数：
                int leftCnt = 0;
                // 该循环的终止条件是找到到左边界的首个奇数
                while (nums[left] % 2 == 0){
                    left++;
                    leftCnt++;
                }

                // 当前可以组合的子数组个数
                res += (leftCnt + 1) * (rightCnt + 1);

                // 去掉当前数组的首个奇数
                left ++;
                oddCnt--;
            }
        }
        return res;
    }

    // 重写
    public int numberOfSubarrays1(int[] nums, int k) {
        // 定义左边界，右边界，滑动窗口内的奇数数量，结果
        int left = 0, right = 0, oddCnt = 0, res = 0;
        // 右边界先行
        while (right < nums.length){
            if (nums[right] % 2 == 1){
                oddCnt++; // 如果遇到奇数，则oddCnt加1
            }
            right++;

            // 当滑动窗口内统计了k个奇数时，找到当前左右边界上连续的偶数个数，计算当前最优美子数组数量
            if (oddCnt == k){
                // 先找到最右边的偶数个数
                int temp = right; //记录right的当前下标
                // 找到右边界上连续的偶数个数，直到遇到奇数退出
                while (right < nums.length && nums[right] % 2 == 0){
                    right++;
                }
                // 获取右边界上偶数的个数
                int rightCnt = right - temp;

                // 继续找到左边界上偶数的个数
                int leftCnt = 0;
                // 直到left指向奇数截止
                while (nums[left] % 2 == 0){
                    left++;
                    leftCnt++;
                }
                // 求出当前滑动窗口的最优子数据结果进行累加
                res += (leftCnt + 1) * (rightCnt + 1);
                // 滑动窗口内退出一个左侧奇数，oddCnt减1，继续寻找下一个
                left++;
                oddCnt--;
            }
        }
        return res;
    }
}
